import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class GenerateFirstSet {
    //保存需要的相关信息
    private List<Formula> formulas;
    private List<String> terminals;
    private List<String> nonTerminals;
    private Map<String, List<String>> firsts;

    public GenerateFirstSet(List<Formula> formulas, List<String> terminals, List<String> nonTerminals, Map<String, List<String>> firsts) {
        this.formulas = formulas;
        this.terminals = terminals;
        this.nonTerminals = nonTerminals;
        this.firsts = firsts;
    }
    public void setFirst() {
        //为每一个终结符创建一个first集合
        List<String> first;
        for(String terminal : terminals) {
            first = new ArrayList<>();
            //每一个终结符的first集合中都含有自己,也只有自己
            first.add(terminal);
            firsts.put(terminal, first);
        }
        //为每一个非终结符创建一个first集合，暂时置空
        for(String nonTerminal : nonTerminals) {
            first = new ArrayList<>();
            firsts.put(nonTerminal, first);
        }

        System.out.println("开始生成first集合-------------------------");
        boolean isChange = true;//只是为了进入循环这样设置
        //循环直到所有的first集合不再发生变化为止
        while (isChange) {
            isChange = false;
            String left, right;
            String[] rights;
            //循环每一个文法规则
            for (Formula f : formulas) {
                left = f.getLeft();
                rights = f.getRight();
                //对每一个规则，遍历其右侧字符集
                for (String s : rights) {
                    right = s;
                    //找到右侧字符集中第一个不是空的字符
                    if (!right.equals("$")) {
                        //此时rights中位于s左侧的都是$，右侧的都不是$
                        //此时说明存在文法left-> $ s ..., 说明s是left的首字符
                        //应该把当前的s的first集合加入到left的first集合中
                        for (String firstStrOfRightSet : firsts.get(right)) {
                            //已经有了就跳过，没有就加入
                            if (firsts.get(left).contains(firstStrOfRightSet) ||
                                    firstStrOfRightSet.equals("$")) {
                                continue;
                            } else {
                                firsts.get(left).add(firstStrOfRightSet);
                                isChange = true;
                            }
                        }
                    }
                    //如果这个s的first集合含有$，则说明还可以继续向后遍历
                    //没有就跳出循环
                    if (isHasNull(right)) {
                        //如果到最后一个right的first集都含有$则给left的first集合加上$
                        if (right.equals(rights[rights.length - 1])) {
                            if (!firsts.get(left).contains("$")) {
                                firsts.get(left).add("$");
                            }
                        }
                        continue;
                    } else {
                        break;
                    }
                }
                System.out.println("字符:" + left + "\t" + "first集:" + firsts.get(left));
            }
        }
    }
    private boolean isHasNull(String symbol) {
        String[] rights;
        for (Formula formula : formulas) {
            //找到产生式
            if (formula.getLeft().equals(symbol)) {
                //symbol -> rights
                rights = formula.getRight();
                if (rights[0].equals("$")) {
                    return true;
                }
            }
        }
        return false;
    }
}
